package com.ww.springboot.boot.algorithm.leetcode1;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * todo
 *
 * @author wanwei
 * @since 2022-03-16 09:52
 */
public class AS77组合3 {

    public static void main(String[] args) {
        int n = 5, k = 3;
        System.out.println(combine(n, k));
    }

    public static List<List<Integer>> combine(int n, int k) {
        if (k > n) {
            return new ArrayList<>();
        }
        List<List<Integer>> list = new ArrayList<>();
        Deque<Integer> path = new ArrayDeque<>();
        combine2(n, k, path, 1, list);

        return list;
    }

    public static void combine2(int n, int k, Deque<Integer> path, int begin, List<List<Integer>> list) {
        if (k == path.size()) {
            list.add(new ArrayList<>(path));
            return;
        }
        //2.剪枝 如果剩下的可选数据 + origin长度小于 k 则不需要再遍历下去了
        if ((n - begin) + path.size() < k - 1) {
            return;
        }
        for (int i = begin; i <= n; i++) {
            path.addLast(i);
            combine2(n, k, path, i + 1, list);
            path.removeLast();
        }
    }
}
